package q719_smallestDistancePair;

import java.util.Arrays;

public class Solution_2 {
    /*
    这里只是想solution1中的第二个问题转化成更容易理解的双指针问题
    不停的移动i 直到不能满足nums[j] - nums[i] > mid为止
    于是就得到了对于当前边界j 能够满足的数对数量
     */
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums[nums.length - 1] - nums[0];
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                int i = 0;
                while (nums[j] - nums[i] > mid) i++;
                count += j - i;
            }

            if (count >= k) {
                r = mid - 1;
            }else {
                l = mid + 1;
            }

        }
        return l;
    }
}
